from functools import cache


## 上界数位dp差
class Solution:
    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:

        si = list(map(int, s))

        def f(mx):
            if int(s) > mx:
                return 0
            n = len(str(mx))
            r = list(map(int, str(mx)))

            @cache
            def ff(index, ul):
                if index == n:
                    return 1
                a = 0
                b = 9 if not ul else r[index]
                ans = 0
                for i in range(a, b + 1):
                    if i <= limit and (
                        n - index > len(s) or i == si[len(s) + index - n]
                    ):
                        ans += ff(index + 1, ul and i == r[index])
                return ans

            return ff(0, True)

        return f(finish) - f(start - 1)


## 同时上下界
class Solution:
    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
        if int(s) > finish:
            return 0
        sa = list(map(int, s))  # 后缀
        fia = list(map(int, str(finish)))  # 结束
        n = len(fia)
        sta = [0] * n
        j = n - 1
        while start > 0:
            sta[j] = start % 10
            start //= 10
            j -= 1

        @cache
        def ff(index, ul):
            if index == n:
                return 1
            a = 0 if ul & 1 != 1 else sta[index]
            b = 9 if ul & 2 != 2 else fia[index]
            ans = 0
            for i in range(a, b + 1):
                if i <= limit and (n - index > len(s) or i == sa[len(s) + index - n]):
                    nu = 2 if ul & 2 == 2 and i == fia[index] else 0
                    nl = 1 if ul & 1 == 1 and i == sta[index] else 0
                    ans += ff(index + 1, nu | nl)
            return ans

        return ff(0, 3)


so = Solution()
print(
    ans := so.numberOfPowerfulInt(start=1000, finish=2000, limit=4, s="3000"), ans == 0
)
print(ans := so.numberOfPowerfulInt(start=1, finish=6000, limit=4, s="124"), ans == 5)
print(ans := so.numberOfPowerfulInt(start=15, finish=215, limit=6, s="10"), ans == 2)
print(ans := so.numberOfPowerfulInt(100568, 99123456, 7, "76123"), ans == 511)
